package algorithm;

import java.util.Stack;

/**
 * @ClassName 合法的出栈序列
 * @Description 已知从1至n的数字序列， 按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，
 * 等待后面的数字入栈出栈后， 该数字再出栈，求该数字序列的出栈序列是否合法？
 * ex：
 * 合法： 3 2 5 4 1
 * 不合法： 3 1 2 4 5
 *
 * @Author wangjq
 * @Date 2021/5/27 22:23
 * @Version 1.0
 **/
public class 合法的出栈序列 {

    public static void main(String[] args) {

        int[] sources=  {3,1,2,4,6,5};

        System.out.println(deal(sources));

    }

    /**
     * 处理逻辑
     * @param sources
     * @return
     */
    private static boolean deal(int[] sources){

        //定义栈
        Stack<Integer> stack = new Stack<Integer>();

        int count = 1;

        for (int i = 0; i < sources.length; i++) {

            while(count<=sources[i]){
                stack.push(count++);
            }

            if(stack.peek() == sources[i]){
                //移除栈顶
                stack.pop();
            }


        }

        if(stack.empty()){
            return true;
        }

        return false;

    }


}
